package org.aplombh.java.interview.newcoder;

import java.util.Scanner;

public class HJ16_购物单 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        Goods[] goods = new Goods[m + 1];
        for (int i = 1; i <= m; i++) {
            goods[i] = new Goods();
        }

        for (int i = 1; i <= m; i++) {
            goods[i].v = in.nextInt();
            goods[i].p = in.nextInt();
            goods[i].q = in.nextInt();

            if (goods[i].q == 0) {  // 主件
                goods[i].main = true;
                goods[i].a[0] = goods[i].v;
                goods[i].b[0] = goods[i].v * goods[i].p;
            }
        }
        for (int i = 1; i <= m; i++) {
            if (!goods[i].main) {
                if (goods[goods[i].q].a[1] == 0) {   // 主件 + 第一个附件
                    goods[goods[i].q].a[1] = goods[i].v + goods[goods[i].q].a[0];
                    goods[goods[i].q].b[1] = goods[i].v * goods[i].p + goods[goods[i].q].b[0];
                } else {    // 主件 + 第二个附件
                    goods[goods[i].q].a[2] = goods[i].v + goods[goods[i].q].a[0];
                    goods[goods[i].q].b[2] = goods[i].v * goods[i].p + goods[goods[i].q].b[0];
                    // 主件 + 第一个附件 + 第二个
                    goods[goods[i].q].a[3] = goods[i].v + goods[goods[i].q].a[1];
                    goods[goods[i].q].b[3] = goods[i].v * goods[i].p + goods[goods[i].q].b[1];
                }
            }
        }

        int[][] f = new int[m + 1][n / 10 + 1];
        // f[i][j] 表示前i件物品，在体积为v的前提下的最大满意度

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n / 10; j++) {
                f[i][j] = f[i - 1][j];
                if (goods[i].main) {
                    for (int k = 0; k < 4; k++) {
                        if (goods[i].a[k] != 0 && goods[i].a[k] / 10 <= j)
                            f[i][j] = Math.max(f[i][j], f[i - 1][j - goods[i].a[k] / 10] + goods[i].b[k]);
                    }
                }
            }
        }

        System.out.println(f[m][n / 10]);
    }
}


class Goods {
    int v;  // 价格
    int p;  // 重要程度
    int q;  // 是否是主件
    boolean main;

    int[] a;    // 价格
    int[] b;    // 价格*重要度

    Goods() {
        a = new int[4];
        b = new int[4];
    }
}